Computerized mapping products are achieving widespread use today. Such mapping programs are commonly used to automate the task of calculating a route from a starting destination to an ending destination. In addition, most mapping programs allow a user to include additional destinations to be visited along the route. Developers of computerized mapping programs are plagued by the problem of ordering the destinations to be visited along the route. More specifically, in the past, developers of computerized mapping programs have had problems providing a mechanism for determining the order in which destinations are visited along the route prior to calculating a route that visits all of the destinations. This problem is sometimes referred to as the "traveling salesman" problem.
In the past, some mapping programs have avoided the problem altogether. Those mapping programs simply calculate a route that visits each destination in the order in which the destinations are provided by a user. That solution is the least optimal because a user rarely provides destinations along a route in an optimal sequence. More likely, a user will simply provide destinations to be visited in a stream-of-consciousness manner. The result may be that the calculated route is substantially longer than optimal.
Other mapping programs address the problem by not ordering the destinations until all of the destinations are input, and then calculating an optimal order for all of the destinations. There are several problems with this approach as well. For example, calculating the true optimal order for the destinations requires comparing each and every possible order of the destinations. That calculation is manageable with three or four destinations, but as the number of destinations increases, the number of calculations necessary quickly overwhelms the computing power of any conventional computer. Consequently, many techniques have been developed to approximate the true optimal solution, such as simulated annealing and other such techniques that result in a highly optimal order for the destinations.
Unfortunately, those techniques still have the disadvantage that they are computationally intensive. The number of computations required to solve the travelling salesman problem still grows rapidly (non-linearly) with the number of destinations. Users of mapping programs do not typically like to wait long periods of time while a mapping program simply orders destinations to be visited even prior to calculating the optimal route. For that reason, if a user inputs several destinations to be visited, using a technique that calculates a highly-optimal order for the destinations introduces unwanted delay.
That undesirable feature of prior mapping programs is particularly undesirable to users that remove or add destinations to an existing list because existing mapping programs, which operate on all of the destinations at once, require a complete reorder of all destinations each time a single new destination is added.
These and other problems render the existing systems and methods less than satisfactory. Until now, a solution to those problems has eluded those skilled in the art. Accordingly, there is a need for a system or method of ordering destinations to be visited that is computationally efficient and achieves an acceptable order based on the total length of a route connecting all of the destinations.